#include "umalloc.h"


// 初始化内存池和空闲块链表
void initialize_mem(){
    free_area = (Block*) mem;       // 指向内存池的起始地址
    free_area->header.size = MEM_BLOCK_SIZE - 1; // 减去header所占的1个页块 
    free_area->header.next = NULL;
    printf("#########内存初始化完成#########\n");
}

// 内存分配函数
void* umalloc(size_t size){     // 形参size的单位是Bytes
    if(size == 0)
        return NULL;

    // 计算需要的页块数目
    size = (size/MIN_BLOCK_SIZE) + !(size%MIN_BLOCK_SIZE);

    Block* prev_block = NULL;
    Block* current_block = free_area;

    while(current_block != NULL){   //  遍历空闲块链表，直到找到适合大小的空闲块
        if(current_block->header.size >= size){  // 采取“首次适应”分配策略
            // 从当前块分配内存
            if(current_block->header.size > size){
                // 拆分块，其中new_block为拆分后的剩余空闲块
                Block* new_block = (Block*)((char*)current_block + size*MIN_BLOCK_SIZE + sizeof(Block));
                new_block->header.size = current_block->header.size - size - 1;
                new_block->header.next = current_block->header.next;
                
                current_block->header.size = size;
                current_block->header.next = new_block;
            }
            // 从空闲块链表中移除刚分配的块
            if(prev_block){
                prev_block->header.next = current_block->header.next;
            }else{
                free_area = current_block->header.next;
            }

            printf("内存分配成功：header_address=%p,size=%d\n", current_block, current_block->header.size);
            return (char*)current_block + sizeof(Block);    // 返回的是header末端地址，即真正可用的内存块的开头
        }
    
        prev_block = current_block;
        current_block = current_block->header.next;
    }
    printf("####内存分配失败####\n");
    return NULL;    // 内存分配失败
}

// 内存释放函数
void ufree(void* ptr){
    if(ptr == NULL)
        return ;
    Block* rel_block = (Block*)((char*)ptr - sizeof(Block));    // 指向该内存块的header，此时header的信息依旧存在
    
    //  将空闲内存块"有序"插入链表中
    Block* prev_block = free_area;
    Block* next_block = free_area->header.next;
    while(next_block != NULL){
        if((prev_block < rel_block) && (next_block > rel_block)){
            prev_block->header.next = rel_block;
            rel_block->header.next = next_block;
            umerge(prev_block);     //  调用碎片整理函数
            return;
        }
        prev_block = next_block;
        next_block = next_block->header.next;
    }

    prev_block->header.next = rel_block;
    rel_block->header.next = NULL;
    umerge(prev_block);     //  调用碎片整理函数
}

// 碎片整理函数
void umerge(Block* prev_block){
    Block* current_block = prev_block->header.next;
    for(size_t i=0; i<2; ++i){      // 只需检查prev、prev->next和prev->next->next之间是否可以合并，其中prev->next是刚释放的内存块
        if(current_block == NULL)
            return;
        if((char*)prev_block + prev_block->header.size*MIN_BLOCK_SIZE + sizeof(Block) == (char*)prev_block->header.next){
            //  合并相邻空闲块
            prev_block->header.size += current_block->header.size + 1;
            prev_block->header.next = current_block->header.next;
        }else{
            prev_block = current_block;
            current_block = current_block->header.next;
        }
    }
}

// 查看空闲块链表函数
void display_free(){
    Block* free_block = free_area;
    printf("####空闲块链表####\n");
    printf("%-3s\t%-10s\t%-5s\t%-10s\t%s\n", "id", "header_address", "size", "start_address", "end_address");
    size_t id = 0;
    while(free_block != NULL){
        printf("%-3d\t%-10p\t%-5d\t%-10p\t%p\n", id, free_block, free_block->header.size, (char*)free_block+sizeof(Block), (char*)free_block+sizeof(Block)+free_block->header.size*MIN_BLOCK_SIZE);
        free_block = free_block->header.next;
        ++id;
    }
    printf("\n");
}

int main(){
    //  初始化内存池和空闲块链表
    initialize_mem();
    //  测试
    void* ptr1 = umalloc(50);
    void* ptr2 = umalloc(100);
    void* ptr3 = umalloc(100);
    void* ptr4 = umalloc(200);
    void* ptr5 = umalloc(100);

    display_free();

    ufree(ptr2);
    printf("释放ptr2\n");
    display_free();
    ufree(ptr5);
    printf("释放ptr5\n");
    display_free();
    ufree(ptr3);
    printf("释放ptr3\n");
    display_free();

    ufree(ptr1);
    ufree(ptr4);
    
    return 0;
}